package l.l.w.CodingInterviews;

/**
 * Created by llw on 2018/3/1.
 */
public class _03_2Problem {
    /**
     * 时间复杂度为O(n)，空间复杂度为O(n)
     * @param numbers
     * @param length
     * @return
     */
    public int duplicate1(int numbers[],int length) {
        int [] temp = new int[length];
        for(int i = 0 ; i < length; ++i){
            if(temp[numbers[i] - 1] == 0){
                temp[numbers[i]-1] = numbers[i];
            }else{
                return numbers[i];
            }
        }
        return 0;
    }

    /**
     * 空间复杂度为O(1)，时间复杂度为O(nlgn)
     * @param numbers
     * @param length
     * @return
     */
    public int duplicate(int numbers[],int length) {

         int start = 1,end = length-1;
         while(end - start >1){
             int  mid = (end+start)/2;
             int preCount = 0, proCount= 0;
             for(int i = 0; i < length; ++i){
                 if(numbers[i] < start || numbers[i] > end) continue;;
                 if(numbers[i] > mid) proCount++;
                 if(numbers[i] <= mid) preCount++;
             }
             if(preCount > (mid - start +1 )){
                 end = mid;
             }else{
                 start = mid + 1;
             }
         }
         if(start == end) return  start;
         int startCount = 0, endCount = 0;
         for(int i = 0; i < length; ++i){
             if(numbers[i] == start)startCount ++;
             if(numbers[i] == end) endCount ++;
         }
         if(startCount > 1) return start;
         return  end;
    }
    public static void main(String[] args) {
        int[] numbers = {2,3,5,4,3,2,6,7};
        int result = new _03_2Problem().duplicate(numbers, numbers.length);
        System.out.println(result);
    }
}
